home *** CD-ROM | disk | FTP | other *** search
/ LG Super CD / LG Super CD.iso / bitpim / bitpim-0.62-setup.exe / {app} / bitpim.exe / difflib.pyo (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2003-11-06  |  17.7 KB  |  518 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyo (Python 2.3)
  3.  
  4. __all__ = [
  5.     'get_close_matches',
  6.     'ndiff',
  7.     'restore',
  8.     'SequenceMatcher',
  9.     'Differ',
  10.     'IS_CHARACTER_JUNK',
  11.     'IS_LINE_JUNK',
  12.     'context_diff',
  13.     'unified_diff']
  14.  
  15. def _calculate_ratio(matches, length):
  16.     if length:
  17.         return 2.0 * matches / length
  18.     
  19.     return 1.0
  20.  
  21.  
  22. class SequenceMatcher:
  23.     
  24.     def __init__(self, isjunk = None, a = '', b = ''):
  25.         self.isjunk = isjunk
  26.         self.a = self.b = None
  27.         self.set_seqs(a, b)
  28.  
  29.     
  30.     def set_seqs(self, a, b):
  31.         self.set_seq1(a)
  32.         self.set_seq2(b)
  33.  
  34.     
  35.     def set_seq1(self, a):
  36.         if a is self.a:
  37.             return None
  38.         
  39.         self.a = a
  40.         self.matching_blocks = self.opcodes = None
  41.  
  42.     
  43.     def set_seq2(self, b):
  44.         if b is self.b:
  45.             return None
  46.         
  47.         self.b = b
  48.         self.matching_blocks = self.opcodes = None
  49.         self.fullbcount = None
  50.         self._SequenceMatcher__chain_b()
  51.  
  52.     
  53.     def __chain_b(self):
  54.         b = self.b
  55.         n = len(b)
  56.         self.b2j = b2j = { }
  57.         populardict = { }
  58.         for i, elt in enumerate(b):
  59.             if elt in b2j:
  60.                 indices = b2j[elt]
  61.                 if n >= 200 and len(indices) * 100 > n:
  62.                     populardict[elt] = 1
  63.                     del indices[:]
  64.                 else:
  65.                     indices.append(i)
  66.             len(indices) * 100 > n
  67.             b2j[elt] = [
  68.                 i]
  69.         
  70.         for elt in populardict:
  71.             del b2j[elt]
  72.         
  73.         isjunk = self.isjunk
  74.         junkdict = { }
  75.         if isjunk:
  76.             for d in (populardict, b2j):
  77.                 for elt in d.keys():
  78.                     if isjunk(elt):
  79.                         junkdict[elt] = 1
  80.                         del d[elt]
  81.                         continue
  82.                 
  83.             
  84.         
  85.         self.isbjunk = junkdict.has_key
  86.         self.isbpopular = populardict.has_key
  87.  
  88.     
  89.     def find_longest_match(self, alo, ahi, blo, bhi):
  90.         (a, b, b2j, isbjunk) = (self.a, self.b, self.b2j, self.isbjunk)
  91.         (besti, bestj, bestsize) = (alo, blo, 0)
  92.         j2len = { }
  93.         nothing = []
  94.         for i in xrange(alo, ahi):
  95.             j2lenget = j2len.get
  96.             newj2len = { }
  97.             for j in b2j.get(a[i], nothing):
  98.                 if j < blo:
  99.                     continue
  100.                 
  101.                 if j >= bhi:
  102.                     break
  103.                 
  104.                 k = newj2len[j] = j2lenget(j - 1, 0) + 1
  105.                 if k > bestsize:
  106.                     (besti, bestj, bestsize) = ((i - k) + 1, (j - k) + 1, k)
  107.                     continue
  108.             
  109.             j2len = newj2len
  110.         
  111.         while besti > alo and bestj > blo and not isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]:
  112.             (besti, bestj, bestsize) = (besti - 1, bestj - 1, bestsize + 1)
  113.         while besti + bestsize < ahi and bestj + bestsize < bhi and not isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]:
  114.             bestsize += 1
  115.         while besti > alo and bestj > blo and isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]:
  116.             (besti, bestj, bestsize) = (besti - 1, bestj - 1, bestsize + 1)
  117.         while besti + bestsize < ahi and bestj + bestsize < bhi and isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]:
  118.             bestsize = bestsize + 1
  119.         return (besti, bestj, bestsize)
  120.  
  121.     
  122.     def get_matching_blocks(self):
  123.         if self.matching_blocks is not None:
  124.             return self.matching_blocks
  125.         
  126.         self.matching_blocks = []
  127.         (la, lb) = (len(self.a), len(self.b))
  128.         self._SequenceMatcher__helper(0, la, 0, lb, self.matching_blocks)
  129.         self.matching_blocks.append((la, lb, 0))
  130.         return self.matching_blocks
  131.  
  132.     
  133.     def __helper(self, alo, ahi, blo, bhi, answer):
  134.         (i, j, k) = x = self.find_longest_match(alo, ahi, blo, bhi)
  135.         if k:
  136.             if alo < i and blo < j:
  137.                 self._SequenceMatcher__helper(alo, i, blo, j, answer)
  138.             
  139.             answer.append(x)
  140.             if i + k < ahi and j + k < bhi:
  141.                 self._SequenceMatcher__helper(i + k, ahi, j + k, bhi, answer)
  142.             
  143.         
  144.  
  145.     
  146.     def get_opcodes(self):
  147.         if self.opcodes is not None:
  148.             return self.opcodes
  149.         
  150.         i = j = 0
  151.         self.opcodes = answer = []
  152.         for ai, bj, size in self.get_matching_blocks():
  153.             tag = ''
  154.             if i < ai and j < bj:
  155.                 tag = 'replace'
  156.             elif i < ai:
  157.                 tag = 'delete'
  158.             elif j < bj:
  159.                 tag = 'insert'
  160.             
  161.             if tag:
  162.                 answer.append((tag, i, ai, j, bj))
  163.             
  164.             (i, j) = (ai + size, bj + size)
  165.             if size:
  166.                 answer.append(('equal', ai, i, bj, j))
  167.                 continue
  168.         
  169.         return answer
  170.  
  171.     
  172.     def get_grouped_opcodes(self, n = 3):
  173.         codes = self.get_opcodes()
  174.         if codes[0][0] == 'equal':
  175.             (tag, i1, i2, j1, j2) = codes[0]
  176.             codes[0] = (tag, max(i1, i2 - n), i2, max(j1, j2 - n), j2)
  177.         
  178.         if codes[-1][0] == 'equal':
  179.             (tag, i1, i2, j1, j2) = codes[-1]
  180.             codes[-1] = (tag, i1, min(i2, i1 + n), j1, min(j2, j1 + n))
  181.         
  182.         nn = n + n
  183.         group = []
  184.         for tag, i1, i2, j1, j2 in codes:
  185.             if tag == 'equal' and i2 - i1 > nn:
  186.                 group.append((tag, i1, min(i2, i1 + n), j1, min(j2, j1 + n)))
  187.                 yield group
  188.                 group = []
  189.                 (i1, j1) = (max(i1, i2 - n), max(j1, j2 - n))
  190.             
  191.             group.append((tag, i1, i2, j1, j2))
  192.         
  193.         if group:
  194.             if len(group) == 1:
  195.                 pass
  196.             if not (group[0][0] == 'equal'):
  197.                 yield group
  198.             
  199.  
  200.     
  201.     def ratio(self):
  202.         matches = reduce((lambda sum, triple: sum + triple[-1]), self.get_matching_blocks(), 0)
  203.         return _calculate_ratio(matches, len(self.a) + len(self.b))
  204.  
  205.     
  206.     def quick_ratio(self):
  207.         if self.fullbcount is None:
  208.             self.fullbcount = fullbcount = { }
  209.             for elt in self.b:
  210.                 fullbcount[elt] = fullbcount.get(elt, 0) + 1
  211.             
  212.         
  213.         fullbcount = self.fullbcount
  214.         avail = { }
  215.         (availhas, matches) = (avail.has_key, 0)
  216.         for elt in self.a:
  217.             if availhas(elt):
  218.                 numb = avail[elt]
  219.             else:
  220.                 numb = fullbcount.get(elt, 0)
  221.             avail[elt] = numb - 1
  222.             if numb > 0:
  223.                 matches = matches + 1
  224.                 continue
  225.         
  226.         return _calculate_ratio(matches, len(self.a) + len(self.b))
  227.  
  228.     
  229.     def real_quick_ratio(self):
  230.         (la, lb) = (len(self.a), len(self.b))
  231.         return _calculate_ratio(min(la, lb), la + lb)
  232.  
  233.  
  234.  
  235. def get_close_matches(word, possibilities, n = 3, cutoff = 0.59999999999999998):
  236.     if not (n > 0):
  237.         raise ValueError('n must be > 0: ' + `n`)
  238.     
  239.     if not None if cutoff <= cutoff else cutoff <= 1.0:
  240.         raise ValueError('cutoff must be in [0.0, 1.0]: ' + `cutoff`)
  241.     
  242.     result = []
  243.     s = SequenceMatcher()
  244.     s.set_seq2(word)
  245.     for x in possibilities:
  246.         s.set_seq1(x)
  247.         if s.real_quick_ratio() >= cutoff and s.quick_ratio() >= cutoff and s.ratio() >= cutoff:
  248.             result.append((s.ratio(), x))
  249.             continue
  250.     
  251.     result.sort()
  252.     result = result[-n:]
  253.     result.reverse()
  254.     return [ x for score, x in result ]
  255.  
  256.  
  257. def _count_leading(line, ch):
  258.     (i, n) = (0, len(line))
  259.     while i < n and line[i] == ch:
  260.         i += 1
  261.     return i
  262.  
  263.  
  264. class Differ:
  265.     
  266.     def __init__(self, linejunk = None, charjunk = None):
  267.         self.linejunk = linejunk
  268.         self.charjunk = charjunk
  269.  
  270.     
  271.     def compare(self, a, b):
  272.         cruncher = SequenceMatcher(self.linejunk, a, b)
  273.         for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():
  274.             if tag == 'replace':
  275.                 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
  276.             elif tag == 'delete':
  277.                 g = self._dump('-', a, alo, ahi)
  278.             elif tag == 'insert':
  279.                 g = self._dump('+', b, blo, bhi)
  280.             elif tag == 'equal':
  281.                 g = self._dump(' ', a, alo, ahi)
  282.             else:
  283.                 raise ValueError, 'unknown tag ' + `tag`
  284.             for line in g:
  285.                 yield line
  286.             
  287.         
  288.  
  289.     
  290.     def _dump(self, tag, x, lo, hi):
  291.         for i in xrange(lo, hi):
  292.             yield '%s %s' % (tag, x[i])
  293.         
  294.  
  295.     
  296.     def _plain_replace(self, a, alo, ahi, b, blo, bhi):
  297.         if bhi - blo < ahi - alo:
  298.             first = self._dump('+', b, blo, bhi)
  299.             second = self._dump('-', a, alo, ahi)
  300.         else:
  301.             first = self._dump('-', a, alo, ahi)
  302.             second = self._dump('+', b, blo, bhi)
  303.         for g in (first, second):
  304.             for line in g:
  305.                 yield line
  306.             
  307.         
  308.  
  309.     
  310.     def _fancy_replace(self, a, alo, ahi, b, blo, bhi):
  311.         (best_ratio, cutoff) = (0.73999999999999999, 0.75)
  312.         cruncher = SequenceMatcher(self.charjunk)
  313.         (eqi, eqj) = (None, None)
  314.         for j in xrange(blo, bhi):
  315.             bj = b[j]
  316.             cruncher.set_seq2(bj)
  317.             for i in xrange(alo, ahi):
  318.                 ai = a[i]
  319.                 if ai == bj:
  320.                     if eqi is None:
  321.                         (eqi, eqj) = (i, j)
  322.                         continue
  323.                     continue
  324.                 
  325.                 cruncher.set_seq1(ai)
  326.                 if cruncher.real_quick_ratio() > best_ratio and cruncher.quick_ratio() > best_ratio and cruncher.ratio() > best_ratio:
  327.                     (best_ratio, best_i, best_j) = (cruncher.ratio(), i, j)
  328.                     continue
  329.             
  330.         
  331.         if best_ratio < cutoff:
  332.             if eqi is None:
  333.                 for line in self._plain_replace(a, alo, ahi, b, blo, bhi):
  334.                     yield line
  335.                 
  336.                 return None
  337.             
  338.             (best_i, best_j, best_ratio) = (eqi, eqj, 1.0)
  339.         else:
  340.             eqi = None
  341.         for line in self._fancy_helper(a, alo, best_i, b, blo, best_j):
  342.             yield line
  343.         
  344.         (aelt, belt) = (a[best_i], b[best_j])
  345.         if eqi is None:
  346.             atags = btags = ''
  347.             cruncher.set_seqs(aelt, belt)
  348.             for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():
  349.                 (la, lb) = (ai2 - ai1, bj2 - bj1)
  350.                 if tag == 'replace':
  351.                     atags += '^' * la
  352.                     btags += '^' * lb
  353.                     continue
  354.                 if tag == 'delete':
  355.                     atags += '-' * la
  356.                     continue
  357.                 if tag == 'insert':
  358.                     btags += '+' * lb
  359.                     continue
  360.                 if tag == 'equal':
  361.                     atags += ' ' * la
  362.                     btags += ' ' * lb
  363.                     continue
  364.                 raise ValueError, 'unknown tag ' + `tag`
  365.             
  366.             for line in self._qformat(aelt, belt, atags, btags):
  367.                 yield line
  368.             
  369.         else:
  370.             yield '  ' + aelt
  371.         for line in self._fancy_helper(a, best_i + 1, ahi, b, best_j + 1, bhi):
  372.             yield line
  373.         
  374.  
  375.     
  376.     def _fancy_helper(self, a, alo, ahi, b, blo, bhi):
  377.         g = []
  378.         if alo < ahi:
  379.             if blo < bhi:
  380.                 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
  381.             else:
  382.                 g = self._dump('-', a, alo, ahi)
  383.         elif blo < bhi:
  384.             g = self._dump('+', b, blo, bhi)
  385.         
  386.         for line in g:
  387.             yield line
  388.         
  389.  
  390.     
  391.     def _qformat(self, aline, bline, atags, btags):
  392.         common = min(_count_leading(aline, '\t'), _count_leading(bline, '\t'))
  393.         common = min(common, _count_leading(atags[:common], ' '))
  394.         atags = atags[common:].rstrip()
  395.         btags = btags[common:].rstrip()
  396.         yield '- ' + aline
  397.         if atags:
  398.             yield '? %s%s\n' % ('\t' * common, atags)
  399.         
  400.         yield '+ ' + bline
  401.         if btags:
  402.             yield '? %s%s\n' % ('\t' * common, btags)
  403.         
  404.  
  405.  
  406. import re
  407.  
  408. def IS_LINE_JUNK(line, pat = re.compile('\\s*#?\\s*$').match):
  409.     return pat(line) is not None
  410.  
  411.  
  412. def IS_CHARACTER_JUNK(ch, ws = ' \t'):
  413.     return ch in ws
  414.  
  415. del re
  416.  
  417. def unified_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'):
  418.     started = False
  419.     for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n):
  420.         if not started:
  421.             yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
  422.             yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
  423.             started = True
  424.         
  425.         (i1, i2, j1, j2) = (group[0][1], group[-1][2], group[0][3], group[-1][4])
  426.         yield '@@ -%d,%d +%d,%d @@%s' % (i1 + 1, i2 - i1, j1 + 1, j2 - j1, lineterm)
  427.         for tag, i1, i2, j1, j2 in group:
  428.             if tag == 'equal':
  429.                 for line in a[i1:i2]:
  430.                     yield ' ' + line
  431.                 
  432.                 continue
  433.             
  434.             if tag == 'replace' or tag == 'delete':
  435.                 for line in a[i1:i2]:
  436.                     yield '-' + line
  437.                 
  438.             
  439.             if tag == 'replace' or tag == 'insert':
  440.                 for line in b[j1:j2]:
  441.                     yield '+' + line
  442.                 
  443.         
  444.     
  445.  
  446.  
  447. def context_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'):
  448.     started = False
  449.     prefixmap = {
  450.         'insert': '+ ',
  451.         'delete': '- ',
  452.         'replace': '! ',
  453.         'equal': '  ' }
  454.     for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n):
  455.         if not started:
  456.             yield '*** %s %s%s' % (fromfile, fromfiledate, lineterm)
  457.             yield '--- %s %s%s' % (tofile, tofiledate, lineterm)
  458.             started = True
  459.         
  460.         yield '***************%s' % (lineterm,)
  461.         if group[-1][2] - group[0][1] >= 2:
  462.             yield '*** %d,%d ****%s' % (group[0][1] + 1, group[-1][2], lineterm)
  463.         else:
  464.             yield '*** %d ****%s' % (group[-1][2], lineterm)
  465.         visiblechanges = []
  466.         if visiblechanges:
  467.             for tag, i1, i2, _, _ in group:
  468.                 if tag != 'insert':
  469.                     for line in a[i1:i2]:
  470.                         yield prefixmap[tag] + line
  471.                     
  472.             
  473.         
  474.         if group[-1][4] - group[0][3] >= 2:
  475.             yield '--- %d,%d ----%s' % (group[0][3] + 1, group[-1][4], lineterm)
  476.         else:
  477.             yield '--- %d ----%s' % (group[-1][4], lineterm)
  478.         visiblechanges = []
  479.         if visiblechanges:
  480.             for tag, _, _, j1, j2 in group:
  481.                 if tag != 'delete':
  482.                     for line in b[j1:j2]:
  483.                         yield prefixmap[tag] + line
  484.                     
  485.             
  486.     
  487.  
  488.  
  489. def ndiff(a, b, linejunk = None, charjunk = IS_CHARACTER_JUNK):
  490.     return Differ(linejunk, charjunk).compare(a, b)
  491.  
  492.  
  493. def restore(delta, which):
  494.     
  495.     try:
  496.         tag = {
  497.             1: '- ',
  498.             2: '+ ' }[int(which)]
  499.     except KeyError:
  500.         raise ValueError, 'unknown delta choice (must be 1 or 2): %r' % which
  501.  
  502.     prefixes = ('  ', tag)
  503.     for line in delta:
  504.         if line[:2] in prefixes:
  505.             yield line[2:]
  506.             continue
  507.     
  508.  
  509.  
  510. def _test():
  511.     import doctest
  512.     import difflib
  513.     return doctest.testmod(difflib)
  514.  
  515. if __name__ == '__main__':
  516.     _test()
  517.  
  518.